package com.itheima.algorithm.binarytree;

import java.util.Arrays;

/**
 * @author: TylerZhong
 * @description:
 * 根据前序中序遍历结果构造二叉树
 */
public class E09Leetcode106 {
    /**
     * preOrder = {1,2,4,3,6,7}
     * inOrder = {4,2,1,6,3,7}
     * @param preOrder
     * @param inOrder
     * @return
     */
    public static TreeNode buildTree(int[] postOrder, int[] inOrder) {
        if (postOrder.length == 0) {
            return null;
        }
        // 根
        int rootValue = postOrder[postOrder.length - 1];
        TreeNode root = new TreeNode(rootValue);
        // 切分左右子树
        for (int i = 0; i < inOrder.length; i++) {
            if (inOrder[i] == rootValue) {
                int[] inLeft = Arrays.copyOfRange(inOrder, 0, i);
                int[] inRight = Arrays.copyOfRange(inOrder, i+1, inOrder.length);

                int[] postLeft = Arrays.copyOfRange(postOrder, 0, i);
                int[] postRight = Arrays.copyOfRange(postOrder, i, postOrder.length-1);

                root.left = buildTree(postLeft, inLeft);
                root.right = buildTree(postRight, inRight);
                break;
            }
        }
        return root;
    }

    public static void main(String[] args) {
        int[] inOrder = {9, 3, 15, 20, 7};
        int[] postOrder = {9,15,7,20,3};
        TreeNode node = buildTree(postOrder, inOrder);
        System.out.println(node);
    }
}
